//Given root of binary search tree and K as input, find K-th smallest element in BST
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<alloc.h>
struct Node
{
       int data;
       struct Node *left;
       struct Node *right;
};
// creates the newNode from given value  and returns the pointer of the newly created node
struct Node *newNode(int value)
{
       struct Node *node = (struct Node*) malloc(sizeof(struct Node));
       node->data = value;
       node->left = NULL;
       node->right = NULL;
       return node;
}
// finds the kth smallest element , processes in the inorder manner and increses the counter , when the counter is equal to k ,
//     then returns the value of the node
int k_smallest_element(Node *root, int n)
{
    static int k=0,element = -1;
    if(root == NULL)
       return element;
    k_smallest_element(root->left, n);
    if(++k == n)
           element = root->data;
    else
           k_smallest_element(root->right, n);
    return element;
}
// finds the Pth smallest element, starts the counter from the rightmost element in the tree, and then increments the counter , returns the value when counter
//  value equals to P
int Pth_largest_element(Node *root, int n)
{
    static int p=0, value = -1;
    if(root == NULL)
        return value;
    Pth_largest_element(root->right, n);
    if(++p == n)
         value = root->data;
    else
        Pth_largest_element(root->left, n);
    return value;
}

int main()
{
    struct Node *root = newNode(24);
    int result;
    root->left = newNode(10);
    root->right = newNode(39);
    root->left->left = newNode(2);
    root->left->right = newNode(14);
    root->right->left = newNode(25);
    root->right->right = newNode(50);
    result = k_smallest_element(root,5);
    printf("\nkth smallest element = %d",result);
    result = Pth_largest_element(root,2);
    printf("\nPth largest element = %d",result);
    getch();
    return 0;
}
